package com.fw.algorithm.find;

/**
 *  差值查找算法
 *  1. 队列必须是有序的，这样效率才高。
 */
public class DifferenceSearch {

    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8,9,10,11};
        System.out.println(differenceSearch(arr,0,arr.length - 1,11));
    }



    /**
     *
     * @param arr  原始数组
     * @param left 左边索引
     * @param right 右边索引
     * @param findVal 要查找的值
     * @return
     */
    public static int differenceSearch(int[] arr,int left,int right,int findVal){
        if (left > right){
            return -1;
        }
        // 开始切割    自适应 全场核心点
        int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);        int midVal = arr[mid];
        // 开始查找
        /**
         * 1. 如果当前中间值比 要查找的数据小 就直接 向右递归
         * 2. 如果当前中间值比 要查找的数据大 就直接 向左递归
         */
        if (midVal < findVal){
            //向右递归
            return differenceSearch(arr, mid + 1, right, findVal);
        }else if (midVal > findVal){
            // 向左递归
            return differenceSearch(arr, mid - 1, right, findVal);
        }else{
            return mid;
        }
    }
}
